﻿#pragma once
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>

#include <algorithm>

#include <time.h>
#include <assert.h>

#include <thread>
#include <mutex>

#ifdef _WIN32
#include <windows.h>
#else
//...
#endif

using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024; //cache能给的最大内存
static const size_t NFREE_LIST = 208; //freeList桶的个数 
static const size_t NPAGES = 129;
static const size_t PAGE_SHIFT = 13;

#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#else
// linux
#endif 

//在堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE,
		PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	//
#endif
}

static void*& NextObj(void* obj)
{
	return *((void**)obj);
}
class FreeList
{
public:
	void Push(void* obj)
	{
		//头插
		NextObj(obj) = _freeList;
		_freeList = obj;

		++_size;
	}
	void* Pop()
	{
		assert(_freeList);
		//头删
		void* obj = _freeList;
		_freeList = NextObj(_freeList);

		--_size;
		return obj;
	}
	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;

		_size += n;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);

		start = _freeList;
		end = start;
		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;

		_size -= n;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t& MaxSize()
	{
		return _maxSize;
	}
	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1; //用于中心缓存慢启动
	size_t _size = 0;
};

class SizeClass
{
public:

	// [1,128] 8byte对齐      					freelist[0,16)
	// [128+1,1024] 16byte对齐  					freelist[16,72)
	// [1024+1,8*1024] 128byte对齐  				freelist[72,128)
	// [8*1024+1,64*1024] 1024byte对齐    		freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对齐  		freelist[184,208)

	
	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		return ((size + alignNum - 1) & ~(alignNum - 1));

		//size_t alignSize;//对齐后的大小
		//if (size % alignNum != 0)
		//{
		//	alignSize = (size / alignNum + 1) * alignNum;
		//}
		//else
		//{
		//	alignSize = size;
		//}
		//return alignSize;
	}
	//计算对齐后的大小
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if(size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8*1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	static inline size_t _Index(size_t bytes, size_t align_shift)//align_shift 对齐数2的指数
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	//计算映射到哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes < MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };

		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8*1024)
		{
			return _Index(bytes - 1024, 7) + group_array[0] + group_array[1];
		}
		else if (bytes <= 64*1024)
		{
			return _Index(bytes - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
		}
		else if (bytes <= 256*1024)
		{
			return _Index(bytes - 64 * 1024, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		}
		else
		{
			assert(false);
			return - 1;
		}
	}

	//thread cache一次从中心缓存获取多少个size大小的内存
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		
		int num = MAX_BYTES / size;
		//[2, 512] 单个对象慢启动的上限值
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

	//计算一次向系统获取几个页
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;

		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;

		return npage;
	}
};

//管理多个连续页大块内存跨度结构
struct Span
{
	PAGE_ID _pageId = 0; //起始页号
	size_t _n = 0;//页的数量

	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _objSize = 0; //切好的小对象的大小，释放内存时使用
	size_t _useCount = 0; //分给thread cache的小块内存的个数
	void* _freeList = nullptr; // 切好的小块内存自由链表

	bool _isUse = false;  //是否在被使用
};

class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		Span* front = Begin();
		//debug
		/////////////////////////////////////////////////////////////
		//char* start = (char*)(front->_pageId << PAGE_SHIFT);
		//size_t bytes = front->_n << PAGE_SHIFT;
		//char* end = start + bytes;

		////把大块内存切成自由链表连接起来
		//front->_freeList = start;
		//start += 16;
		//void* tail = front->_freeList;

		//while (start < end)
		//{
		//	NextObj(tail) = start;
		//	tail = NextObj(tail);
		//	start += 16;
		//}
		//NextObj(tail) = nullptr;
		/////////////////////////////////////////////////////////////////
		Erase(Begin());
		return front;
	}
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos != _head);
		assert(pos);

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;

	}
private:
	Span* _head;
public:
	std::mutex _mtx;
};